#include <iostream>
#include <stack>
#include <vector>

using namespace std;
// 150.逆波兰表达式求值
// 逆波兰表达式求职。给定一个字符串数组，表示一个逆波兰表达式。求其值。
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> nums;
        for(const string& s: tokens) {
            // 处理运算符
            if(s == "+" || s == "-" || s == "*" || s == "/") {
                // 取出两个数
                int a = nums.top();
                nums.pop();
                int b = nums.top();
                nums.pop();

                if(s == "+")
                    nums.push(b+a);
                else if(s == "-")
                    nums.push(b-a);
                else if(s == "*")
                    nums.push(b*a);
                else if(s == "/")
                    nums.push(b/a);
            } else
                nums.push(atoi(s.c_str()));
        }
        return nums.top();
    }
};
int main() {
    vector<string> tokens = {"2","1","+","3","*"};
    cout << Solution().evalRPN(tokens) << endl; // 9

    tokens = {"4","13","5","/","+"};
    cout << Solution().evalRPN(tokens) << endl; // 6

    tokens = {"10","6","9","3","+","-11","*","/","*","17","+","5","+"};
    cout << Solution().evalRPN(tokens) << endl; // 22

    return 0;
}
